package com.example.leetcode.trainingcamp.week9.sunday;

/**
 * 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。
 *
 * 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
 *
 * 注意，不管是什么情况下，你都无法跳到数组之外。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：arr = [4,2,3,0,3,1,2], start = 5
 * 输出：true
 * 解释：
 * 到达值为 0 的下标 3 有以下可能方案：
 * 下标 5 -> 下标 4 -> 下标 1 -> 下标 3
 * 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1306 {

    boolean is = false;

    boolean[] visit;

    public boolean canReach(int[] arr, int start) {
        visit = new boolean[arr.length];
        visit[start] = true;
        dfs(arr,start);
        return is;
    }

    public void dfs(int[] arr,int start){
        int i = arr[start];
        if (i == 0) {
            is = true;
            return;
        }
        if (start - i >=0){
            if (!visit[start -i]){
                visit[start -i] = true;
                dfs(arr,start-i);
            }
        }
        if (start+i<arr.length){
            if (!visit[start+i]){
                visit[start+i] = true;
                dfs(arr,start+i);
            }
        }
    }
}

class Demo1306{
    public static void main(String[] args) {
        int[] arr = {4,2,3,0,3,1,2};
        int start = 0;
        Test1306 t = new Test1306();
        System.out.println(t.canReach(arr, start));
    }
}